package com.lishem.carl._02linkedlist;

import com.lishem.common.ListNode;

/**
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
 * <p>
 * 给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null 。
 */
public class _6LetCode160_相交链表 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur = headA;
        int lenA = 0;
        while (cur != null) {
            cur = cur.next;
            lenA++;
        }
        int lenB = 0;
        cur = headB;
        while (cur != null) {
            cur = cur.next;
            lenB++;
        }
        ListNode fast, slow;
        int dif = 0;
        if (lenA > lenB) {
            dif = lenA - lenB;
            fast = headA;
            slow = headB;
        } else {
            dif = lenB - lenA;
            fast = headB;
            slow = headA;
        }

        while (dif-- > 0) {
            fast = fast.next;
        }
        while (fast != slow && fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast == slow ? fast : null;
    }


    public static void main(String[] args) {
        _6LetCode160_相交链表 sol = new _6LetCode160_相交链表();
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = new ListNode(8);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = new ListNode(5);
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next = headA.next.next;
        System.out.println(sol.getIntersectionNode(headA, headB).val); // 8

    }
}
